`:top

Ein `!Out-Tree`! oder auch `!Arboreszenz`! ist in der `F33f`_`[Graphentheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graphentheorie]`_`f ein spezieller `F33f`_`[Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graph_(Graphentheorie)]`_`f, genauer ein `F33f`_`[gewurzelter Baum`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gewurzelter_Baum]`_`f, bei dem die Kanten von der Wurzel ausgehen. Der Gegensatz dazu ist der sogenannte `F33f`_`[In-Tree`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=In-Tree]`_`f.

>>Contents

• `F0af`_`[Definition`#definition]`_`f

• `F0af`_`[Weitere Begriffe`#weitere-begriffe]`_`f

• `F0af`_`[Alternative Definition`#alternative-definition]`_`f

• `F0af`_`[Siehe auch`#siehe-auch]`_`f

• `F0af`_`[Literatur`#literatur]`_`f

• `F0af`_`[Einzelnachweise`#einzelnachweise]`_`f

-─

>>Definition

Eine Arboreszenz ist ein `F33f`_`[gerichteter`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gerichteter_Graph]`_`f Graph mit einem ausgezeichneten Knoten, der so genannten `F33f`_`[Wurzel`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Wurzel_(Graphentheorie)]`_`f, sodass jeder Knoten durch genau einen `F33f`_`[gerichteten Pfad`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gerichteter_Pfad]`_`f von der Wurzel aus erreichbar ist.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]

>>Weitere Begriffe

Der maximale `F33f`_`[Ausgangsgrad`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Ausgangsgrad]`_`f wird als `*Ordnung`* eines Out-Trees bezeichnet und alle Knoten mit Ausgangsgrad 0 bezeichnet man als `F33f`_`[Blätter`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Blatt_(Graphentheorie)]`_`f. Als `F33f`_`[Tiefe`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Tiefe_(Graphentheorie)]`_`f eines Knotens bezeichnet man die Länge des Pfades von der Wurzel zu ihm und als `F33f`_`[Höhe`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Höhe_(Graphentheorie)]`_`f des Out-Trees die Länge eines längsten Pfades.

Wie bei `F33f`_`[ungerichteten Bäumen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Ungerichteter_Baum]`_`f bezeichnet man auch in gewurzelten Bäumen alle Knoten, die kein Blatt sind, als `F33f`_`[innere Knoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Innerer_Knoten]`_`f. Manchmal schließt man die Wurzel dabei aber aus.

Bei einem `F33f`_`[(a,b)-Baum`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=(a,b)-Baum]`_`f haben alle Teilbäume die gleiche Tiefe.

`:vorfahr`aFür einen von der Wurzel verschiedenen Knoten `*v`* bezeichnet man den Knoten, durch den er mit einer eingehenden Kante verbunden ist als `*Vater`*, `*Vaterknoten`*, `F33f`_`[Elternknoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gewurzelter_Baum]`_`f oder `*Vorgänger`* von `*v`*. Als `*Vorfahren`* von `*v`* bezeichnet man alle Knoten, die entweder Vater von `*v`* oder Vorgänger des Vaters sind.

Umgekehrt bezeichnet man alle Knoten, die von einem beliebigen Knoten `*v`* aus durch eine ausgehende Kante verbunden sind als `*Kinder`*, `F33f`_`[Kindknoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gewurzelter_Baum]`_`f, `*Sohn`* oder `*Nachfolger`* von `*v`*. Als `*Nachfahren`* von `*v`* bezeichnet man Kinder von `*v`* oder deren Nachfahren. Als `*Geschwister`* oder `*Geschwisterknoten`* werden in einer Arboreszenz Knoten bezeichnet, die denselben `*Vater`* besitzen.

>>Alternative Definition

Out-Trees lassen sich auch `F33f`_`[rekursiv`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Rekursion]`_`f definieren. Sie bestehen aus einem `F33f`_`[Knoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Knoten_(Graphentheorie)]`_`f `*w`*, der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter Out-Trees `*T`*1, `*T`*2, ..., `*T`*`*n`* verbunden ist, und zwar in Richtung der Wurzeln von `*T`*1, `*T`*2, ..., `*T`*`*n`*.

>>Siehe auch

• Der `F33f`_`[letzte gemeinsame Vorfahr`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Lowest_Common_Ancestor]`_`f als Ermittlungskonzept in der Graphentheorie

>>Literatur

• Bernhard Korte, Jens Vygen: Aufspannende Bäume und Arboreszenzen. In: Kombinatorische Optimierung: Theorie und Algorithmen. Springer, Berlin, Heidelberg 2018, ISBN 978-3-662-57691-5, S. 141–166, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1007/978-3-662-57691-5_6 (springer.com).

>>Einzelnachweise

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f Willibald Dörfler, Jörg Mühlbacher: Graphentheorie für Informatiker. Walter de Gruyter, 2011, ISBN 978-3-11-083572-4, S. 49 f. (google.de [abgerufen am 31. Dezember 2024]).

`c`F0af`_`[↑ Back to top`#top]`_`f`a